package cn.springcloud.fix.demo.leecode;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Stack;

public class TwoSum {

    //两数之和
    public static void main(String[] args) {
        int[] arr = {51, 2, 33, 12, 100};
        int[] res = twoSum(arr, 112);
        for (int i : res) {
            System.out.print(i + "\t");
        }
        int num = reverse(-123);
        boolean val = isValid("{[]}");
    }

    public static int lengthOfLongestSubstring(String s) {
        int max = 0;
        Map<Character, Integer> map = new HashMap<>();
        char[] arr = s.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            if (map.containsKey(arr[i])) {//重复了
                Integer index = map.get(arr[i]);
                max = Math.max(max, i - index);
            }
            map.put(arr[i], i);
        }
        return max;
    }

    // https://leetcode-cn.com/problems/add-two-numbers/
    // public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    //     ListNode head = null, tail = null;
    //     int carry = 0;
    //     while (l1 != null || l2 != null) {
    //         int n1 = l1 != null ? l1.getVal() : 0;
    //         int n2 = l2 != null ? l2.getVal() : 0;
    //         int sum = n1 + n2 + carry;
    //
    //         if (head == null) {
    //             head = tail = new ListNode(sum % 10);
    //         } else {
    //             tail.next = new ListNode(sum % 10);
    //             tail = tail.next;
    //         }
    //
    //         carry = sum / 10;
    //         if (l1 != null) {
    //             l1 = l1.next;
    //         }
    //         if (l2 != null) {
    //             l2 = l2.next;
    //         }
    //     }
    //     if (carry > 0) {
    //         tail.next = new ListNode(carry);
    //     }
    //     return head;
    // }


    //有效的括号 "{[]}"
    public static boolean isValid(String s) {
        LinkedList<Character> stack = new LinkedList<>();
        for (char c : s.toCharArray()) {
            if (c == '[')
                stack.push(']');
            else if (c == '(')
                stack.push(')');
            else if (c == '{')
                stack.push('}');
            else if (stack.isEmpty() || c != stack.pop())
                return false;
        }
        return stack.isEmpty();
    }

    //有效的括号
    public boolean isValid2(String s) {
        if (s == null || s.length() == 0) return false;
        while (s.contains("{}") || s.contains("[]") || s.contains("()")) {
            s = s.replace("{}", "");
            s = s.replace("()", "");
            s = s.replace("[]", "");
        }
        return s.isEmpty();
    }

    //整数反转
    public static int reverse(int x) {
        long res = 0;
        while (x != 0) {
            res = res * 10 + x % 10;
            x = x / 10;
        }
        return (int) res;
    }

    //两数之和
    public static int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }

    //两数之和
    public static int[] twoSum2(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; ++i) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{map.get(target - nums[i]), i};
            }
            map.put(nums[i], i);
        }
        return new int[0];
    }
}
